Viterbi decoders are well known in the art as maximum likelihood decoders which can be used in systems that employ error correcting codes, such as convolutional codes, trellis codes, and a variety of other codes, all of which can be generally characterized by a so-called trellis. The basic concept of the Viterbi decoder can be described as correlating all possible transmitted sequences with the received sequence and then choosing as the "best" or "maximum likelihood" path the sequence whose correlation is maximum.
In particular, the trellis encoder in a transmitting modem proceeds through a sequence of so-called states which, in turn, defines a corresponding sequence of signal point subsets of a signal constellation. Indeed, a feature of trellis coding is that, at any point in time, only the points in particular subsets of the constellation are allowed to be transmitted, depending on the state of the trellis encoder.
A trellis associated with the particular trellis code being utilized by the modem consists of a sequence of concatenations of a so-called trellis diagram, or state transition diagram. The trellis diagram defines, for each code state, which next state or states the encoder is allowed to transition to. The allowable transitions from one state to a next, subsequent state are limited. Each such transition is associated with one of the constellation subsets, such that when the encoder transitions from a particular current state to one of the allowed next states, a signal point will be output by the transmitter which is taken from the subset associated with that state transition. Each possible transition from one state to a next state is called a branch. Each branch, therefore, corresponds to a subset. A sequence of signal points selected from a sequence of interconnected branches is called a path through the trellis.
The transmitted signal points are displaced in signal space due to noise and channel-induced distortion, and the receiver uses the Viterbi decoder, operating on the received version of the transmitted signal points, to perform the aforementioned maximum likelihood sequence detection. Based on the received version of the transmitted signal points and the knowledge of the trellis code used by the encoder, the Viterbi decoder determines the most likely sequence of signal points that was actually transmitted. The decoder performs this function by forming a tentative decision as to what was the most likely transmitted signal point that would have caused the encoder to transition into a next state of the code. These tentative decisions are signal points along the so-called "surviving paths" which are certain paths through the trellis.
More particularly, the Viterbi decoder forms the surviving paths by keeping track of so-called "metrics". A branch metric, a function of the received version of the signal point, is calculated for each current-to-next-state transition associated with each branch in the trellis diagram. More particularly, the branch metric for each branch is determined by the distance between the received signal point and the closest signal point in the subset associated with that branch. Every path through the trellis which leads into a state has an associated path metric which is a function of the sum of the branch metrics for the branches that make up that particular path. Further, a path entering a current state may be extended through the trellis and enter a next state by including a branch representing an allowed transition from the current state to the next state. The path metric for such an extended path is a function of the sum of (a) the path metric associated with the path as it entered the current state and (b) the branch metric associated with the included branch.
The decoder compares the path metrics of the different paths entering a state and retains as one of the aforementioned surviving paths the path with the smallest path metric. All other paths entering that state are discarded. The surviving paths are used by the decoder to make a final decision as to the value of an earlier transmitted signal point.
Prior to being applied to the Viterbi decoder, each received signal point is typically processed to compensate, at least to some extent, for the aforementioned channel impairments. It is well known, for example, to use a so-called feedforward equalizer to remove at least a portion of the so-called intersymbol inteference ("ISI") component of the received signal. The ISI-compensated signal point is then used in calculating the branch metric for each branch. Although feedforward equalizers work well for channels in which the ISI is relatively mild, severe ISI is typically more effectively compensated for using a so-called decision feedback equalizer ("DFE"). Such an equalizer generates an estimate of the ISI component of a received signal point as a function of decisions as to the values of previously received signal points. As noted above, the nature of Viterbi decoding is such however that those decisions have not yet been made at the time that the ISI estimate is needed. U.S. Pat. No. 5,056,117 issued to Gitlin et al. addresses this issue. In the joint DFE/Viterbi decoder disclosed therein, a separate DFE is provided for each surviving path and the "decisions" used by each DFE are the aforementioned tentative decisions along that surviving path.